package org.zhangyp.n02datastructure.n04Queue;

import java.util.Arrays;

/**
 * 用数组实现一个队列
 *
 * @param <E>
 */
public class MyArrayQueue<E> implements MyQueue<E> {
    private Object[] data; // 数据
    private int head = 0; // 头
    private int tail = 0; // 尾
    private int size; // 队列大小，初始为0

    public MyArrayQueue(int cap) {
        this.data = new Object[cap];
    }

    @Override
    public void push(E item) {
        // 判断队列是否已经满了
        if (size == data.length) {
            throw new IndexOutOfBoundsException("队列已满");
        }
        // 队尾已到达数组尾部，但队列未满，将现有的数据移动到数组最前边
        if (tail == data.length) {
            //统一移动
            int i = 0;
            for (; i < tail - head; i++) {
                data[i] = data[head + i];
            }
            // 剩余数据置空
            while (i < data.length) {
                data[i++] = null;
            }
            head = 0;
            tail = size;
        }
        System.out.println(Arrays.toString(data) + "  size=" + size);
        data[tail++] = item;
        size++;
        System.out.println(Arrays.toString(data) + "  size=" + size);
    }

    @Override
    public E pop() {
        if (isEmpty()) {
            return null;
        }
        E res = (E) data[head++];
        size--;
        return res;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    public static void main(String[] args) {
        MyArrayQueue<Integer> queue = new MyArrayQueue<>(3);
        queue.push(1);
        queue.push(2);
        queue.push(3);
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        queue.push(4);
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());
    }
}
